#include "TreeGenerator.h"
#include "IdNode.h"

#include <vector>
#include <deque>

namespace jcrada {

    TreeGenerator::TreeGenerator() :
    _functions_arity(3),
    _min_terminal_value(0.0),
    _max_terminal_value(1.0),
    _preferred_method(M_RAMPED),
    _preferred_depth(2),
    _random_node(new RandomNode()),
    _random_method(new RandomGsl()),
    _random_id(new RandomGsl()),
    _random_arity(new RandomGsl()) {

    }

    TreeGenerator::~TreeGenerator() {
        delete _random_node;
        delete _random_method;
        delete _random_id;
        delete _random_arity;
    }

    Node* TreeGenerator::createRandomSubtree() {
        return createRandomSubtree(getPreferredDepth(), getPreferredMethod());
    }

    Node* TreeGenerator::createRandomSubtree(int depth) {
        return createRandomSubtree(depth, getPreferredMethod());
    }

    Node* TreeGenerator::createRandomSubtree(int depth, eMethod method) {
        Node* result = NULL;
        if (method == M_RAMPED) {
            method = getRandomMethod().nextBool() ? M_FULL : M_GROW;
        }
        switch (method) {
            case M_FULL:
                if (depth > 0) {
                    result = getRandomNode().nextFunction(getFunctionsArity());
                    for (int i = 0; i < result->getArity(); ++i) {
                        createRandomSubtree(depth - 1, method)->moveTo(result, i);
                    }
                } else {
                    result = getRandomNode().nextTerminal(getMinTerminalValue(), getMaxTerminalValue());
                }
                break;
            case M_GROW:
                if (depth > 0) {
                    result = getRandomNode().next(getMinTerminalValue(), getMaxTerminalValue(), getFunctionsArity());
                    for (int i = 0; i < result->getArity(); ++i) {
                        createRandomSubtree(depth - 1, method)->moveTo(result, i);
                    }
                } else {
                    result = getRandomNode().nextTerminal(getMinTerminalValue(), getMaxTerminalValue());
                }
                break;
            default:
                DEBUGM(TO_STRING(method));
                assert(0);
        }
        return result;
    }

    TreeOfNodes* TreeGenerator::createRandomTree() {
        return createRandomTree(getPreferredDepth(), getPreferredMethod());
    }

    TreeOfNodes* TreeGenerator::createRandomTree(int depth) {
        return createRandomTree(depth, getPreferredMethod());
    }

    TreeOfNodes* TreeGenerator::createRandomTree(int depth, eMethod method) {
        TreeOfNodes* result = new TreeOfNodes();
        Node* root = getRandomNode().nextFunction(getFunctionsArity());
        result->setRoot(root);
        for (int i = 0; i < getFunctionsArity(); ++i) {
            createRandomSubtree(depth - 1, method)->moveTo(root, i);
        }
        return result;
    }

    void TreeGenerator::createBinarySubtree(int size, Node** nodes) {
        Node* parent = NULL;
        int tree_size = 0;
        for (int i = 0; i < size; ++i) {
            parent = nodes[i];
            for (int j = 1; j <= 2; ++j) {
                if (2 * i + j >= size) {
                    return;
                }
                if (parent->canHaveAnotherChild()) {
                    nodes[2 * i + j]->moveTo(parent);
                    ++tree_size;
                }
            }
        }
    }
    //[0,max_arity)

    void TreeGenerator::createRandomIdSubtree(IdNode& parent, int* size, int max_arity, std::vector<int>& ids) {
        if (*size == 0) {
            return;
        }
        IdNode* child = NULL;
        int arity = -1;
        int pos_id = -1;
        int id = -1;
        for (int i = 0; i < parent.getArity() && *size > 0; ++i) {
            arity = getRandomArity().nextInt(0, max_arity);
            pos_id = getRandomId().nextInt(0, ids.size());
            id = ids.at(pos_id);
            ids.erase(ids.begin() + pos_id);
            child = new IdNode(arity, id);
            child->moveTo(&parent, i);
            --*size;
        }
        for (int i = 0; i < parent.getArity() && *size > 0; ++i) {
            child = dynamic_cast<IdNode*> (parent.getChild(i));
            assert(child);
            createRandomIdSubtree(*child, size, max_arity, ids);
        }
    }

    IdNode* TreeGenerator::createRandomIdSubtree(int size, int starting_id) {
        IdNode* root = NULL;
        bool meets_size = false;
        int* size_ptr = new int;
        std::vector<int> ids;
        int tries = 0;
        while (!meets_size) {
            ++tries;
            ids.clear();
            for (int i = starting_id; i < size; ++i) {
                ids.push_back(i);
            }
            int arity = getRandomArity().nextInt(0, size);
            int pos_id = getRandomId().nextInt(0, ids.size());
            int id = ids.at(pos_id);
            ids.erase(ids.begin() + pos_id);
            if (root) delete root;
            root = new IdNode(arity, id);
            *size_ptr = size - 1;
            createRandomIdSubtree(*root, size_ptr, size, ids);
            meets_size = root->getTreeSize() == size;
        }
        delete size_ptr;
        //        BDEBUG(" " + TO_STRING(tries) + " intentos para crear el árbol del tamaño correcto");
        return root;
    }

    TreeOfNodes* TreeGenerator::createRandomIdTree(int size, int starting_id) {
        TreeOfNodes* result = new TreeOfNodes();
        result->setRoot(createRandomIdSubtree(size, starting_id));
        return result;
    }

    void TreeGenerator::copyAndRemove(IdNode** nodes, int number_of_nodes, std::vector<IdNode*>& result) {
        BDEBUG("\n" + nodes[0]->toXml());
        result.push_back(nodes[0]->clone());
        for (int i = 0; i < number_of_nodes; ++i) {
            nodes[i]->remove();
        }
    }

    void TreeGenerator::createAllSubtreeForN4(std::vector<IdNode*>& result) {
        int number_of_nodes = 4;
        IdNode** n = new IdNode*[number_of_nodes];
        for (int i = 0; i < number_of_nodes; ++i) {
            n[i] = new IdNode(number_of_nodes - 1,i);
        }
        //5 combinaciones en 3 soluciones
        //s_{1} = 3l_{1} = 1
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{2} = 1l_{1} + 2l_{2} = 3
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{3} = 3l_{3} = 1
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        copyAndRemove(n, number_of_nodes, result);

        assert(result.size() == 5);
        for (int i = 0; i < number_of_nodes; ++i) {
            delete n[i];
        }
        delete [] n;
    }

    void TreeGenerator::createAllSubtreeForN5(std::vector<IdNode*>& result) {
        int number_of_nodes = 5;
        IdNode** n = new IdNode*[number_of_nodes];
        for (int i = 0; i < number_of_nodes; ++i) {
            n[i] = new IdNode(number_of_nodes - 1,i);
        }
        //14 combinaciones en 5 soluciones.
        //s_{1} = 4l_{1} = 1
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{2} = 2l_{1} + 1l_{2} = 6
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(5)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(6)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{3} = 1l_{1} + 1l_{3} = 4
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{4} = 2l_{2} = 2
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{5} = 1l4 = 1
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[0]);
        copyAndRemove(n, number_of_nodes, result);

        assert(result.size() == 14);
        for (int i = 0; i < number_of_nodes; ++i) {
            delete n[i];
        }
        delete [] n;
    }

    void TreeGenerator::createAllSubtreeForN6(std::vector<IdNode*>& result) {
        int number_of_nodes = 6;
        IdNode** n = new IdNode*[number_of_nodes];
        for (int i = 0; i < number_of_nodes; ++i) {
            n[i] = new IdNode(number_of_nodes - 1,i);
        }
        //42 combinaciones en 7 soluciones.
        //s_{1} = 5l_{1} = 1
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{2} = 2l_{1} + 1l_{3} = 10
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(5)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(6)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(7)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(8)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(9)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(10)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{3} = 2l_{1} + 1l_{3} = 10
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(5)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(6)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(7)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(8)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(9)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(10)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{4} = 1l_{4} + 1l_{1} = 5
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[0]);
        n[5]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[0]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[0]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[0]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(5)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{5} = 1l_{1} + 2l_{2} = 10
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[1]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(5)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(6)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(7)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(8)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[4]);
        copyAndRemove(n, number_of_nodes, result);
        //(9)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //(10)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{6} = 1l_{2} + 1l_{3} = 5
        //(1)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[1]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(2)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[2]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(3)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[1]);
        n[5]->moveTo(n[1]);
        copyAndRemove(n, number_of_nodes, result);
        //(4)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[2]);
        n[5]->moveTo(n[2]);
        copyAndRemove(n, number_of_nodes, result);
        //(5)
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[3]);
        n[5]->moveTo(n[3]);
        copyAndRemove(n, number_of_nodes, result);
        //s_{7} = 5l_{1} = 1
        n[1]->moveTo(n[0]);
        n[2]->moveTo(n[0]);
        n[3]->moveTo(n[0]);
        n[4]->moveTo(n[0]);
        n[5]->moveTo(n[0]);
        copyAndRemove(n, number_of_nodes, result);

        assert(result.size() == 42);
        for (int i = 0; i < number_of_nodes; ++i) {
            delete n[i];
        }
        delete [] n;
    }

    void TreeGenerator::createAllSubtrees(int number_of_nodes, std::vector<IdNode*>& result) {
        switch (number_of_nodes) {
            case 4: createAllSubtreeForN4(result);
                break;
            case 5:createAllSubtreeForN5(result);
                break;
            case 6: createAllSubtreeForN6(result);
                break;
            default:
                BDEBUG(TO_STRING(number_of_nodes));
                assert(0);
        }
    }

    std::vector<TreeOfNodes*>* TreeGenerator::createAllTrees(int number_of_nodes){
        std::vector<TreeOfNodes*>* result = new std::vector<TreeOfNodes*>;
        std::vector<IdNode*>* roots = new std::vector<IdNode*>;
        createAllSubtrees(number_of_nodes,*roots);
        for (int i = 0 ; i < roots->size(); ++i){
            result->push_back(new TreeOfNodes(roots->at(i)));
        }
        delete roots;
        return result;
    }

    void TreeGenerator::tmp(int size) {
        if (size > 0) {
            BDEBUG(TO_STRING(size));
            //        for (int i = size ; i > 0; --i){
            //            BDEBUG(TO_STRING(i));
            tmp(size - 1);
        }
        //        }
    }

    void printChilds(const Node* node) {
        //BFS
        int result = 0;
        std::deque<const Node*> deque;
        deque.push_back(node);
        while (deque.size() > 0) {
            node = deque.front();
            //            DEBUG(TO_STRING(dynamic_cast<const IdNode*>(node)->getId()));
            BDEBUG(node->toString());
            for (int i = 0; i < node->getArity(); ++i) {
                if (node->getChild(i) != NULL) {
                    deque.push_back(node->getChild(i));
                }
            }
            deque.pop_front();
        }
        //        return result;

    }

    int TreeGenerator::main(int argc, char** argv) {
        std::vector<IdNode*> result;
        createAllSubtreeForN6(result);
        BDEBUG("????");
        BDEBUG(TO_STRING((int)result.size()));
        for (int i = 0; i < result.size(); ++i) {
            BDEBUG(TO_STRING(i));
            BDEBUG("\n" + result.at(i)->toXml());
        }
    }
}
